42

Beginner’s Guide to Code Algorithms

42

STEP 5 continued

      Next k

        If howmanycantbe =​ 8 Then

          sbox(i, j) =​ 45 -​ whatisthisnumber

          Cells(i, j) =​ sbox(i, j)

          Call updatecantbelist(sbox(i, j), i, j)

        End If

      End If

    Next j

  Next i

continue =​ InputBox(“Iteration” & Iteration & “complete. Continue?Y/​N”)

If continue <> “Y” Then End

Next Iteration

3.3  ALGORITHMS THAT A COMPUTER CAN SOLVE BETTER THAN

HUMANS

So far whatever we have done using code is doable comfortably by a human—​it just

takes longer but the logic is reasonably straightforward. If you have done serious

Sudoku, you would have come across some puzzles that are extremely hard. You may

be staring at the puzzle for hours until the light fades and you realize that it is time

to turn on the table lamp! These are the types of puzzles that need us to venture into

further algorithms without which we just cannot solve the puzzle completely.

One such algorithm is to find 8 cells in a row, column, or 3 by 3 grid that is defin­

itely not a certain number from 1 to 9. If that is the case, then the ninth cell must be

that number. This is the principle behind the code in steps 6, 7, and 8.

STEP 6

check all columns row by row for all numbers 1–​9 (putnumber)

if the number is invalid in 8 of the nine cells in the same row, then the number must

belong to the ninth cell (empty, of course).

For putnumber =​ 1 to 9

  For i =​ 1 To 9

    numberfound =​ 0

if the number we are searching for (putnumber) already exists in this row, then no

need to proceed. This is controlled through the value of variable numberfound, by

setting it to “1” and ignoring it for the rest of the code if this number already exists

  For j =​ 1 To 9

    If sbox(i, j) =​ putnumber Then numberfound =​ 1

  Next j

“notahome” is a variable that is used to flag an empty cell if the cantbelist array

contains the number we are searching for (putnumber) number we are searching for

(putnumber) because this cell is “not a home” for it. A count is kept in the variable

“notahomecount” to determine how many cells in this row have banished this

number. This is because if eight cells have, then the ninth cell must be this number.

  If numberfound =​ 0 Then

    notahomecount =​ 0